#include <stdlib.h>

template<typename T>
void CountingSort(T *vec, size_t cnt,int low,int up)
{
	int normUp = up-low+1;
	if(normUp<2)
	{
		printf("Input (up - low) must larger than 2!\n");
		exit(1);
	}
	int *pCnt = new int[normUp];
	T* pNorm = new T[cnt];
	memset(pCnt,0,sizeof(int)*normUp);
	for(size_t i=0; i<cnt;i++)
	{
		pNorm[i]=vec[i]-low;
		if(pNorm[i]<0)
		{
			printf("Error: element in index %d is smaller than input lowest %d\n",i,low);
			exit(1);
		}
	}
	for(size_t i=0; i<cnt;i++)
		pCnt[pNorm[i]]++;
	for(size_t i=1; i<normUp;i++)
		pCnt[i]+=pCnt[i-1];
	for(int i=cnt-1; i>=0;i--)
	{
		vec[pCnt[pNorm[i]]-1]=pNorm[i]+low;
		pCnt[pNorm[i]]--;
	}
	delete []pNorm;
	delete []pCnt;
}